package com.cn.algorithm02.class22;

/***
 * @author: hels
 * @description: arr是面值数组，其中值都是正数且没有重复；在给定一个正数aim；数组中的每个数都认为是一种面值，
 * 且认为是无限张。返回组成aim的方法数。
 * 解题思路：
 *  记忆化搜索方法
 *  严格表结构，中查看规律。
 **/
public class C03_CoinsWayNoLimit {
    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 5, 6,10};
        int aim = 200;
        System.out.println(process(arr, 0, aim));
        System.out.println(dp(arr, aim));
        System.out.println(dp2(arr, aim));
    }

    /** 优化：记忆化搜索方法
     * 通过观察严格表结构发现，dp的值只跟下边和左边的一个值有关。
     * dp[index][rest] = dp[index + 1][rest];
     * if (rest - arr[index] >= 0) {
     *    dp[index][rest] += dp[index][rest  - arr[index]];
     * }
     */
    public static int dp2(int[] arr, int aim) {
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;

        for (int index = N -1; index >=0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                dp[index][rest] = dp[index + 1][rest];
                if (rest - arr[index] >= 0) {
                    dp[index][rest] += dp[index][rest  - arr[index]];
                }
            }
        }
        return dp[0][aim];
    }

    /**动态规划，严格表结构形式计算*/
    public static int dp(int[] arr, int aim) {
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;

        for (int index = N -1; index >=0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                int ways = 0;
                for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
                    ways += dp[index+1][rest - zhang * arr[index]];
                }
                dp[index][rest] = ways;
            }
        }

        return dp[0][aim];
    }

    /**递归方法
     */
    public static int process(int[] arr, int index, int rest) {
        if (index == arr.length) {
            return rest == 0 ? 1 : 0;
        }
        int ways = 0;
        for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
            ways += process(arr, index+1, rest - zhang * arr[index]);
        }
        return ways;
    }
}
